/* 

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */

// 迭代
var reverseBetween = function (head, m, n) {
    let count = n - m + 1;

    let dummyHead = p = new ListNode();
    dummyHead.next = head;

    let pre, cur, front, tail;

    for (let i = 0; i < m - 1; i++) {
        p = p.next;
    }
    pre = front = p;
    cur = tail = pre.next;

    while (count--) {
        const next = cur.next;
        cur.next = pre
        pre = cur;
        cur = next;
    }

    front.next = pre;
    tail.next = cur;

    return dummyHead.next;
};

// 递归
var reverseBetween = function (head, m, n) {
    const reverse = function (pre, cur) {
        if (!cur) return pre;
        let next = cur.next;
        cur.next = pre;
        return reverse(cur, next);
    }

    let count = n - m + 1;

    let dummyHead = p = new ListNode();
    dummyHead.next = head;

    let start, end, front, tail;

    for (let i = 0; i < m - 1; i++) {
        p = p.next;
    }

    front = p;
    start = p.next;

    for (let i = 0; i < count; i++) {
        p = p.next;
    }

    end = p;
    tail = p.next;
    end.next = null;

    front.next = reverse(null, start);
    start.next = tail;

    return dummyHead.next;
};